#include <iostream>
#include <string>
#include <cassert>
#include <fstream>
#include "arraylist.h"
#include "arraystack.h"

using namespace std;

class Transition
{
	private:
		int srcState;
		char readSym;
		char popSym;
		int dstState;
		char pushSym;
	
	public:
		
		Transition() : srcState(0), readSym(' '), popSym(' '), dstState(0), pushSym(' ') {}
		Transition(int src, char rdsym, char popsym, int dst, char pshsym) :
			srcState(src), readSym(rdsym), popSym(popsym), dstState(dst), pushSym(pshsym) {}
		
		int Src() const {return srcState;}
		char ReadSym() const {return readSym;}
		char PopSym() const {return popSym;}
		int Dst() const {return dstState;}
		char PushSym() const {return pushSym;}
		
		void input(istream& in);
		void output(ostream& out) const;
};

void Transition::input(istream& in)
{
	char c;
	in >> c;
	assert(c == '(');
	in >> srcState;
	in >> c;
	assert(c == ',');
	in >> readSym;
	in >> c;
	assert(c == ',');
	in >> popSym;
	in >> c;
	assert(c == ';');
	in >> dstState;
	in >> c;
	assert(c == ',');
	in >> pushSym;
	in >> c;
	assert(c == ')');
	return;
}

void Transition::output(ostream& out) const
{
	out << '(' << srcState << ", " << readSym << ", " << popSym
		<< "; " << dstState << ", " << pushSym << ')';
	return;
}

istream& operator>>(istream& in, Transition& t);

istream& operator>>(istream& in, Transition& t)
{
	t.input(in);
	return in;
}

ostream& operator<<(ostream& out, const Transition& t);

ostream& operator<<(ostream& out, const Transition& t)
{
	t.output(out);
	return out;
}

int findTransition(int currState, char currSymbol, char stkSymbol, ArrayList<Transition>& delta);

int main()
{
	ArrayList<Transition> delta;
	ArrayList<int> final;
	ArrayStack<char> stack;
	
//	Read the DFA from the file machine.txt

	cout << "Enter the DPDA file name: ";
	string fileName;
	cin >> fileName;
	fstream fin(fileName.c_str());
	if (!fin)
	{
		cerr << "Failed to open " << fileName << endl;
		exit(1);
	}
	
	fin >> delta;
	fin >> final;
	
//	Process the string on the input tape

	int currState = 0;
	char currSymbol;
	bool rejected = false;
	bool done = false;
	
	cout << "Enter the input string: ";
	
	cin >> currSymbol;
	while (!rejected && (cin || !stack.Empty()))
	{
		int trans;
		char stkSym;
		if (!stack.Empty() && cin)		// Stack is not empty and string is not done
		{
			stkSym = stack.Top();
			trans = findTransition(currState, currSymbol, stkSym, delta);
			if (trans == -1)
			{
				trans = findTransition(currState, 'e', stkSym, delta);
				if (trans == -1)
				{
					trans = findTransition(currState, currSymbol, 'e', delta);
					if (trans == -1)
					{
						trans = findTransition(currState, 'e', 'e', delta);
						if (trans == -1)
							rejected = true;
					}
				}
			}
		}
		else if (stack.Empty() && cin)
		{
			trans = findTransition(currState, currSymbol, 'e', delta);
			if (trans == -1)
			{
				trans = findTransition(currState, 'e', 'e', delta);
				if (trans == -1)
					rejected = true;
			}
		}
		else if (!stack.Empty() && !cin)
		{
			stkSym = stack.Top();
			trans = findTransition(currState, 'e', stkSym, delta);
			if (trans == -1)
			{
				trans = findTransition(currState, 'e', 'e', delta);
				if (trans == -1)
					rejected = true;
			}
		}
		else
		{
			trans = findTransition(currState, 'e', 'e', delta);
			if (trans == -1)
				rejected = true;
		}
		
		if (!rejected)
		{
			if (delta[trans].PopSym() != 'e')
				stack.Pop();
				
			currState = delta[trans].Dst();
			stkSym = delta[trans].PushSym();
			if (stkSym != 'e')
				stack.Push(stkSym);
			cout << "Stack = " << stack << endl;
			
			if (delta[trans].ReadSym() != 'e')
				cin >> currSymbol;
		}
		else
		{
			if (!cin)
				currSymbol = 'e';
			if (stack.Empty())
				stkSym = 'e';
				
			cout << "Read " << currSymbol << " and pop " << stkSym << "; move from state "
				 << currState << " to the implicit reject state" << endl;
		}
	}
	
	if (!rejected && final.Search(currState) > 0 && stack.Empty())
		cout << "The string is accepted" << endl;
	else
		cout << "The string is rejected" << endl;
	
	return 0;
}

int findTransition(int currState, char currSymbol, char stkSymbol, ArrayList<Transition>& delta)
{
	for (int i = 1; i <= delta.Size(); i++)
		if (delta[i].Src() == currState && delta[i].ReadSym() == currSymbol && delta[i].PopSym() == stkSymbol)
		{
			cout << "Read " << currSymbol << " and pop " << stkSymbol << "; move from state "
				 << currState << " to state " << delta[i].Dst() << " and push "
				 << delta[i].PushSym() << ". ";
			return i;
		}

	return -1;
}